#include <string>
#include <vector>
using namespace std;
bool isValid(string s) {
  vector<char> stack;
  for (auto c : s) {
    if (stack.empty()) {
      stack.push_back(c);
    } else {
      if (c == '}') {
        if (stack.back() == '{')
          stack.pop_back();
        else
          return false;
      }
      if (c == ']') {
        if (stack.back() == '[')
          stack.pop_back();
        else
          return false;
      }
      if (c == ')') {
        if (stack.back() == '(')
          stack.pop_back();
        else
          return false;
      }
      if (c == '(')
        stack.push_back('(');
      if (c == '[')
        stack.push_back('[');
      if (c == '{')
        stack.push_back('{');
    }
  }
  if (stack.empty())
    return true;
  return false;
}